#pragma once

template<typename T>
class CLinkedStack
{
private:
    struct Node {
        Node(Node* pNext = nullptr)
            : m_pNext(pNext)
        {
        }

        Node(T data, Node* pNext = nullptr)
            :m_data(data), m_pNext(pNext)
        {
        }

        T m_data;
        Node* m_pNext;
    };

public:
    CLinkedStack()
    {
        m_pHead = new Node();
    }
    ~CLinkedStack()
    {
        clear();
        delete m_pHead;
    }

    void push(const T& elem)
    {
        m_pHead->m_pNext = new Node(elem, m_pHead->m_pNext);
    }

    void pop()
    {
        Node* pDel = m_pHead->m_pNext;
        m_pHead->m_pNext = pDel->m_pNext;
        delete pDel;
    }

    T peek() const
    {
        return m_pHead->m_pNext->m_data;
    }

    bool empty() const
    {
        return m_pHead->m_pNext == nullptr;
    }

    void clear()
    {
        Node* pDel = m_pHead->m_pNext;
        while (pDel != nullptr)
        {
            Node* pNext = pDel->m_pNext;
            delete pDel;
            pDel = pNext;
        }
    }
private:
    Node* m_pHead;
};


template<typename T>
class CArrayStack
{
private:
    struct Node {
        Node(Node* pNext = nullptr)
            : m_pNext(pNext)
        {
        }

        Node(T data, Node* pNext = nullptr)
            :m_data(data), m_pNext(pNext)
        {
        }

        T m_data;
        Node* m_pNext;
    };

public:
    CArrayStack(int nSize = 1)
    {
        m_pBuf = new T[nSize];
        m_nSize = 0;
    }
    ~CArrayStack()
    {
        delete[] m_pBuf;
    }

    void push(const T& elem)
    {
        m_pBuf[m_nSize++] = elem;
    }

    void pop()
    {
        m_nSize--;
    }

    T peek() const
    {
        return m_pBuf[m_nSize - 1];
    }

    bool empty() const
    {
        return m_nSize == 0;
    }

    int size() const
    {
        return m_nSize;
    }

    void clear()
    {
        m_nSize = 0;
    }
private:
    T* m_pBuf;
    int m_nSize;
};

